using System;
using System.Drawing;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace Hoshimi
{


	#region Class CustomQueue

	/// <summary>
	/// Implements a strongly typed first-in, first-out collection
	/// of <see cref="Point"/> elements.
	/// </summary>
	/// <remarks>
	/// <b>CustomQueue</b> provides a <see cref="Queue"/>
	/// that is strongly typed for <see cref="Point"/> elements.
	/// </remarks>

	[Serializable]
	public class CustomQueue<T> : ICloneable
	{
		#region Private Fields

		private const int _defaultCapacity = 32;
		private const int _minimumGrow = 4;

		private T[] _array = null;
		private int _growFactor, _head, _tail, _count;

		[NonSerialized]
		private int _version = 0;

		#endregion
		#region Private Constructors

		// helper type to identify private ctor
		private enum Tag { Default }

		private CustomQueue(Tag tag) { }

		#endregion
		#region Public Constructors
		#region CustomQueue()

		/// <overloads>
		/// Initializes a new instance of the <see cref="CustomQueue"/> class.
		/// </overloads>
		/// <summary>
		/// Initializes a new instance of the <see cref="CustomQueue"/> class that is
		/// empty, has the default initial capacity, and uses the default growth factor.
		/// </summary>
		/// <remarks>Please refer to <see cref="Queue()"/> for details.</remarks>

		public CustomQueue() : this(_defaultCapacity, 2f) { }

		#endregion
		#region CustomQueue(Int32)

		/// <summary>
		/// Initializes a new instance of the <see cref="CustomQueue"/> class that is
		/// empty, has the specified initial capacity, and uses the default growth factor.
		/// </summary>
		/// <param name="capacity">The number of elements that the new
		/// <see cref="CustomQueue"/> is initially capable of storing.</param>
		/// <exception cref="ArgumentOutOfRangeException">
		/// <paramref name="capacity"/> is less than zero.</exception>
		/// <remarks>Please refer to <see cref="Queue(Int32)"/> for details.</remarks>

		public CustomQueue(int capacity) : this(capacity, 2f) { }

		#endregion
		#region CustomQueue(Int32, Single)

		/// <summary>
		/// Initializes a new instance of the <see cref="CustomQueue"/> class that is
		/// empty, has the specified initial capacity, and uses the specified growth factor.
		/// </summary>
		/// <param name="capacity">The number of elements that the new
		/// <see cref="CustomQueue"/> is initially capable of storing.</param>
		/// <param name="growFactor">The factor by which the capacity of the
		/// <see cref="CustomQueue"/> is expanded when necessary.</param>
		/// <exception cref="ArgumentOutOfRangeException"><para>
		/// <paramref name="capacity"/> is less than zero.
		/// </para><para>-or-</para><para>
		/// <paramref name="growFactor" /> is less than 1.0 or greater than 10.0.
		/// </para></exception>
		/// <remarks>Please refer to <see cref="Queue(Int32, Single)"/> for details.</remarks>

		public CustomQueue(int capacity, float growFactor)
		{
			if (capacity < 0)
				throw new ArgumentOutOfRangeException("capacity",
					capacity, "Argument cannot be negative.");

			if (growFactor < 1f || growFactor > 10f)
				throw new ArgumentOutOfRangeException("growFactor",
					growFactor, "Argument cannot be less than 1.0 or greater than 10.0.");

			this._array = new T[capacity];
			this._growFactor = (int)(growFactor * 100f);
		}

		#endregion
		#region CustomQueue(IPointCollection)


		#endregion
		#region CustomQueue(Point[])

		/// <summary>
		/// Initializes a new instance of the <see cref="CustomQueue"/> class that
		/// contains elements copied from the specified <see cref="Point"/>
		/// array, has the same initial capacity as the number of elements copied,
		/// and uses the default growth factor.
		/// </summary>
		/// <param name="array">An <see cref="Array"/> of <see cref="Point"/>
		/// elements that are copied to the new collection.</param>
		/// <exception cref="ArgumentNullException">
		/// <paramref name="array"/> is a null reference.</exception>
		/// <remarks>Please refer to <see cref="Queue(ICollection)"/> for details.</remarks>

		public CustomQueue(T[] array)
		{
			if (array == null)
				throw new ArgumentNullException("array");

			this._array = new T[array.Length];
			this._growFactor = 200;

			foreach (T item in array)
				Enqueue(item);
		}

		#endregion
		#endregion
		#region Public Properties
		#region Count

		/// <summary>
		/// Gets the number of elements contained in the <see cref="CustomQueue"/>.
		/// </summary>
		/// <value>
		/// The number of elements contained in the <see cref="CustomQueue"/>.
		/// </value>
		/// <remarks>Please refer to <see cref="Queue.Count"/> for details.</remarks>

		public virtual int Count
		{
			get { return this._count; }
		}

		#endregion
		#region IsSynchronized

		/// <summary>
		/// Gets a value indicating whether access to the <see cref="CustomQueue"/>
		/// is synchronized (thread-safe).
		/// </summary>
		/// <value><c>true</c> if access to the <see cref="CustomQueue"/> is
		/// synchronized (thread-safe); otherwise, <c>false</c>. The default is <c>false</c>.</value>
		/// <remarks>Please refer to <see cref="Queue.IsSynchronized"/> for details.</remarks>

		public virtual bool IsSynchronized
		{
			get { return false; }
		}

		#endregion
		#region SyncRoot

		/// <summary>
		/// Gets an object that can be used to synchronize
		/// access to the <see cref="CustomQueue"/>.
		/// </summary>
		/// <value>An object that can be used to synchronize
		/// access to the <see cref="CustomQueue"/>.
		/// </value>
		/// <remarks>Please refer to <see cref="Queue.SyncRoot"/> for details.</remarks>

		public virtual object SyncRoot
		{
			get { return this; }
		}

		#endregion
		#endregion
		#region Public Methods
		#region Clear

		/// <summary>
		/// Removes all elements from the <see cref="CustomQueue"/>.
		/// </summary>
		/// <remarks>Please refer to <see cref="Queue.Clear"/> for details.</remarks>

		public virtual void Clear()
		{
			if (this._count == 0) return;
			++this._version;

			if (this._head < this._tail)
				Array.Clear(this._array, this._head, this._count);
			else
			{
				Array.Clear(this._array, this._head, this._array.Length - this._head);
				Array.Clear(this._array, 0, this._tail);
			}

			this._head = this._tail = this._count = 0;
		}

		#endregion
		#region Clone

		/// <summary>
		/// Creates a shallow copy of the <see cref="CustomQueue"/>.
		/// </summary>
		/// <returns>A shallow copy of the <see cref="CustomQueue"/>.</returns>
		/// <remarks>Please refer to <see cref="Queue.Clone"/> for details.</remarks>

		public virtual object Clone()
		{
			CustomQueue<T> collection = new CustomQueue<T>(this._count);

			for (int i = 0; i < this._count; i++)
				collection._array[i] = GetByIndex(i);

			collection._tail = collection._count = this._count;
			collection._version = this._version;

			return collection;
		}

		#endregion
		#region Contains

		/// <summary>
		/// Determines whether the <see cref="CustomQueue"/>
		/// contains the specified <see cref="Point"/> element.
		/// </summary>
		/// <param name="value">The <see cref="Point"/> object
		/// to locate in the <see cref="CustomQueue"/>.
		/// </param>
		/// <returns><c>true</c> if <paramref name="value"/> is found in the
		/// <see cref="CustomQueue"/>; otherwise, <c>false</c>.</returns>
		/// <remarks>Please refer to <see cref="Queue.Contains"/> for details.</remarks>

		public virtual bool Contains(T value)
		{


			for (int i = 0; i < this._count; i++)
				if (value.Equals(GetByIndex(i)))
					return true;

			return false;
		}

		#endregion
		#region CopyTo(T[])

		/// <overloads>
		/// Copies the <see cref="CustomQueue"/> or a portion of it to a one-dimensional array.
		/// </overloads>
		/// <summary>
		/// Copies the entire <see cref="CustomQueue"/> to a one-dimensional <see cref="Array"/>
		/// of <see cref="Point"/> elements, starting at the beginning of the target array.
		/// </summary>
		/// <param name="array">The one-dimensional <see cref="Array"/> that is the destination of the
		/// <see cref="Point"/> elements copied from the <see cref="CustomQueue"/>.
		/// The <b>Array</b> must have zero-based indexing.</param>
		/// <exception cref="ArgumentNullException">
		/// <paramref name="array"/> is a null reference.</exception>
		/// <exception cref="ArgumentException">
		/// The number of elements in the source <see cref="CustomQueue"/> is greater
		/// than the available space in the destination <paramref name="array"/>.</exception>
		/// <remarks>Please refer to <see cref="Queue.CopyTo"/> for details.</remarks>

		public virtual void CopyTo(T[] array)
		{
			CheckTargetArray(array, 0);
			for (int i = 0; i < this._count; i++)
				array[i] = GetByIndex(i);
		}

		#endregion
		#region CopyTo(Point[], Int32)

		/// <summary>
		/// Copies the entire <see cref="CustomQueue"/> to a one-dimensional <see cref="Array"/>
		/// of <see cref="Point"/> elements, starting at the specified index of the target array.
		/// </summary>
		/// <param name="array">The one-dimensional <see cref="Array"/> that is the destination of the
		/// <see cref="Point"/> elements copied from the <see cref="CustomQueue"/>.
		/// The <b>Array</b> must have zero-based indexing.</param>
		/// <param name="arrayIndex">The zero-based index in <paramref name="array"/>
		/// at which copying begins.</param>
		/// <exception cref="ArgumentNullException">
		/// <paramref name="array"/> is a null reference.</exception>
		/// <exception cref="ArgumentOutOfRangeException">
		/// <paramref name="arrayIndex"/> is less than zero.</exception>
		/// <exception cref="ArgumentException"><para>
		/// <paramref name="arrayIndex"/> is equal to or greater than the length of <paramref name="array"/>.
		/// </para><para>-or-</para><para>
		/// The number of elements in the source <see cref="CustomQueue"/> is greater than the
		/// available space from <paramref name="arrayIndex"/> to the end of the destination
		/// <paramref name="array"/>.</para></exception>
		/// <remarks>Please refer to <see cref="Queue.CopyTo"/> for details.</remarks>

		public virtual void CopyTo(T[] array, int arrayIndex)
		{
			CheckTargetArray(array, arrayIndex);
			for (int i = 0; i < this._count; i++)
				array[arrayIndex + i] = GetByIndex(i);
		}

		#endregion

		#region Dequeue

		/// <summary>
		/// Removes and returns the <see cref="Point"/> element
		/// at the beginning of the <see cref="CustomQueue"/>.
		/// </summary>
		/// <returns>The <see cref="Point"/> object removed from
		/// the beginning of the <see cref="CustomQueue"/>.</returns>
		/// <exception cref="InvalidOperationException">
		/// The <see cref="CustomQueue"/> is empty.</exception>
		/// <remarks>Please refer to <see cref="Queue.Dequeue"/> for details.</remarks>

		public virtual T Dequeue()
		{
			if (this._count == 0)
				throw new InvalidOperationException("Collection is empty.");

			++this._version;
			T item = this._array[this._head];
			this._array[this._head] = default(T);

			this._head = (this._head + 1) % this._array.Length;
			--this._count;
			return item;
		}

		#endregion
		#region Enqueue

		/// <summary>
		/// Adds a <see cref="Point"/> to the 
		/// end of the <see cref="CustomQueue"/>.
		/// </summary>
		/// <param name="value">The <see cref="Point"/> object
		/// to add to the end of the <see cref="CustomQueue"/>.
		/// </param>
		/// <remarks>Please refer to <see cref="Queue.Enqueue"/> for details.</remarks>

		public virtual void Enqueue(T value)
		{

			if (this._count == this._array.Length)
			{
				int newCapacity = (int)(((long)this._array.Length * this._growFactor) / 100);
				if (newCapacity < this._array.Length + _minimumGrow)
					newCapacity = this._array.Length + _minimumGrow;
				SetCapacity(newCapacity);
			}

			++this._version;
			this._array[this._tail] = value;
			this._tail = (this._tail + 1) % this._array.Length;
			++this._count;
		}

		#endregion

		#region Peek

		/// <summary>
		/// Returns the <see cref="Point"/> element at the beginning
		/// of the <see cref="CustomQueue"/> without removing it.
		/// </summary>
		/// <returns>The <see cref="Point"/> object at the 
		/// beginning of the <see cref="CustomQueue"/>.</returns>
		/// <exception cref="InvalidOperationException">
		/// The <see cref="CustomQueue"/> is empty.</exception>
		/// <remarks>Please refer to <see cref="Queue.Peek"/> for details.</remarks>

		public virtual T Peek()
		{
			if (this._count == 0)
				throw new InvalidOperationException("Collection is empty.");

			return this._array[this._head];
		}

		#endregion

		#region ToArray

		/// <summary>
		/// Copies the elements of the <see cref="CustomQueue"/> to a new
		/// <see cref="Array"/> of <see cref="Point"/> elements.
		/// </summary>
		/// <returns>A one-dimensional <see cref="Array"/> of <see cref="Point"/>
		/// elements containing copies of the elements of the <see cref="CustomQueue"/>.</returns>
		/// <remarks>Please refer to <see cref="Queue.ToArray"/> for details.</remarks>

		public virtual T[] ToArray()
		{
			T[] array = new T[this._count];

			for (int i = 0; i < this._count; i++)
				array[i] = GetByIndex(i);

			return array;
		}

		#endregion
		#region TrimToSize

		/// <summary>
		/// Sets the capacity to the actual number of elements in the <see cref="CustomQueue"/>.
		/// </summary>
		/// <exception cref="NotSupportedException">
		/// <para>The <see cref="CustomQueue"/> is read-only.</para>
		/// <para>-or-</para>
		/// <para>The <b>CustomQueue</b> has a fixed size.</para></exception>
		/// <remarks>Please refer to <see cref="Queue.TrimToSize"/> for details.</remarks>

		public virtual void TrimToSize()
		{
			SetCapacity(this._count);
		}

		#endregion
		#endregion
		#region Private Methods
		#region CheckEnumIndex

		private void CheckEnumIndex(int index)
		{
			if (index < 0 || index >= this._count)
				throw new InvalidOperationException(
					"Enumerator is not on a collection element.");
		}

		#endregion
		#region CheckEnumVersion

		private void CheckEnumVersion(int version)
		{
			if (version != this._version)
				throw new InvalidOperationException(
					"Enumerator invalidated by modification to collection.");
		}

		#endregion
		#region CheckTargetArray

		private void CheckTargetArray(Array array, int arrayIndex)
		{
			if (array == null)
				throw new ArgumentNullException("array");
			if (array.Rank > 1)
				throw new ArgumentException(
					"Argument cannot be multidimensional.", "array");

			if (arrayIndex < 0)
				throw new ArgumentOutOfRangeException("arrayIndex",
					arrayIndex, "Argument cannot be negative.");
			if (arrayIndex >= array.Length)
				throw new ArgumentException(
					"Argument must be less than array length.", "arrayIndex");

			if (this._count > array.Length - arrayIndex)
				throw new ArgumentException(
					"Argument section must be large enough for collection.", "array");
		}

		#endregion
		#region GetByIndex

		private T GetByIndex(int index)
		{
			return this._array[(this._head + index) % this._array.Length];
		}

		#endregion
		#region SetCapacity

		private void SetCapacity(int capacity)
		{
			T[] array = new T[capacity];
			for (int i = 0; i < this._count; i++)
				array[i] = GetByIndex(i);

			++this._version;
			this._array = array;
			this._head = 0;
			this._tail = this._count;
		}

		#endregion
		#endregion

	#endregion
	}

}
